//不同路径--1
class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<vector<size_t>> dp(m);
        for(auto& e : dp)
        {
            e.resize(n);
        }
        
        for(size_t x = 0 ; x < n ; ++x)
        {
            dp[0][x] = 1;
        }
        for(size_t y = 0 ; y < m ; ++y)
        {
            dp[y][0] = 1;
        }
        int finish_x = m-1;
        int finish_y = n-1;
        for(size_t i = 1 ; i < m ; ++i)
        {
            for(size_t j = 1 ; j < n ; ++j)
            {
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }
        return dp[finish_x][finish_y];
    }
};

//不同路径--2
class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        // dp状态表示：以[i][j]位置为结尾，到达[i][j]的总方法数
        int m = obstacleGrid.size();
        int n = obstacleGrid[0].size();
        vector<vector<size_t>> dp(m + 1); // 添加虚拟行方便初始化
        for (size_t y = 0; y <= m; ++y) {
            dp[y].resize(n+1);
        }
        dp[0][1] = 1;
        for (size_t x = 1; x <= m; ++x) {

            for (size_t y = 1; y <= n; ++y) {
                if(obstacleGrid[x-1][y-1] == 1)
                {
                    dp[x][y] = 0;
                    continue;
                }
                else 
                {
                    dp[x][y] = dp[x-1][y] + dp[x][y-1];
                }
            }
        }
        return dp[m][n];
    }
};

//珠宝的最高价值
class Solution {
public:
    int jewelleryValue(vector<vector<int>>& frame) {
        int m = frame.size();
        int n = frame[0].size();
        //dp的状态表示:到达[i][j]位置时，拿取的最大价值
        //dp[i][j] = max(dp[i-1][j],dp[i][j-1])
        vector<vector<size_t>> dp(m+1);
        for(size_t y = 0 ; y <= m ; ++y)
        {
            dp[y].resize(n+1);
        }
        for(size_t y = 1 ; y <= m ; ++y)
        {
            for(size_t x = 1 ; x <= n ; ++x)
            {
                dp[y][x] = max(dp[y-1][x],dp[y][x-1])+frame[y-1][x-1];
            }
        }
        return dp[m][n];
    }
};

//下降路径最小和
class Solution {
public:
    int minFallingPathSum(vector<vector<int>>& matrix) {
        //dp状态表示下降到该位置时的最小和
        //状态转移方程:dp[i][j] = min(dp[i-1][j],dp[i-1][j-1],dp[i-1][j+1])+matrix[i][j]
        int m = matrix.size();
        int n = matrix[0].size();
        vector<vector<int>> dp(m+1);
        for(size_t y = 0 ; y <= m ; ++y)
        {
            dp[y].resize(n+2);
            if(y > 0)
            {
                dp[y][0] = INT_MAX;
                dp[y][n+1] = INT_MAX;
            }
        }
        for(size_t y = 1 ; y <= m ; ++y)
        {
            for(size_t x = 1 ; x <= n ; ++x)
            {
                int min = dp[y-1][x];
                if(dp[y-1][x-1] < min)
                    min = dp[y-1][x-1];
                
                if(dp[y-1][x+1] < min)
                    min = dp[y-1][x+1];
                dp[y][x] = min+matrix[y-1][x-1];
            }
        }
        int min = INT_MAX;
        for(size_t i = 1 ; i <= n ; ++i)
        {
            if(dp[m][i] < min)
                min = dp[m][i];
        }
        return min;
    }
};

//最小路径和
class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        //dp的状态表示：以[i][j]位置为结尾，到达该位置的最小路径总和
        //dp[i][j] = min(dp[i-1][j],dp[i][j-1])+grid[i][j]
        int m = grid.size();
        int n = grid[0].size();
        vector<vector<size_t>> dp(m+1);
        for(size_t y = 0 ; y < dp.size() ; ++y)
        {
            dp[y].resize(n+1,UINT_MAX);
        }
        dp[0][1] = dp[1][0] = 0;
        for(size_t y = 1 ; y <= m ; ++y)
        {
            for(size_t x = 1 ; x <= n ; ++x)
            {
                dp[y][x]=min(dp[y-1][x],dp[y][x-1]) + grid[y-1][x-1];
            }
        }

        return dp[m][n];
    }
};

//地下城游戏
class Solution {
public:
    int calculateMinimumHP(vector<vector<int>>& dungeon) {
        //dp的状态表示：以[i][j]位置为起点，从该位置到达终点所需的最少初始健康点数
        //dp[i][j] = max(dp[i+1][j],dp[i][j+1])-dungeon[i][j];
        int m = dungeon.size();
        int n = dungeon[0].size();
        vector<vector<int>> dp(m+1,vector<int>(n+1,INT_MAX));
        dp[m][n-1] = dp[m-1][n] = 1;
        for(int y = m-1 ; y >= 0 ; --y)
        {
            for(int x = n-1 ; x >= 0 ; --x)
            {
                dp[y][x] = min(dp[y+1][x],dp[y][x+1])-dungeon[y][x];
                dp[y][x] = max(1,dp[y][x]);//防止血包过大，dp变为负数不合理
            }
        }
        return dp[0][0];
    }
};